

#p和q采用rabin算法求出后，求出私钥d 解出flag

c2 =  8943014059616554864780402232625215323717650137702921347505099596041241060991211014413068279308600979202066026580321911322396296877730441259506201930904989
p1 =  9332664074116371272320347910722305705338764655969305966836353509444565128652866496870138156351793824473079367512299950127043084761943406224989567423866071
c3 =  70057129621004770704688083264954773868924488489858841648741006057913061247128697063230635204818097097989773079555422507429472690950271096686354023051578709918278343598395904697714639469429943421928621364157106993940737884253250276769074919155850720804529008723376094183112401317966966358905432385347745890161
p2 =  8345774537268501775456149547604093811537369706242159709058405913660493926215699313366059497170577713800176152866821540944395025269529309431564563983026047
q2 =  10391251387900816431089217882564594263543706933015218000664649428273018708690965953263846227725465978045419390050088292820030415626410428034269853834640767

import libnum
import gmpy2

p = pow(c2, (p1 + 1) // 4, p1)
print(p)
print(c2==pow(p,2,p1))

e=2
n=p2*q2
inv_p = gmpy2.invert(p2, q2)
inv_q = gmpy2.invert(q2, p2)
mp = pow(c3, (p2 + 1) // 4, p2)
mq = pow(c3, (q2 + 1) // 4, q2)
a = (inv_p * p2 * mq + inv_q * q2 * mp) % n
b = n - int(a)
c = (inv_p * p2 * mq - inv_q * q2 * mp) % n
d = n - int(c)
# 因为rabin 加密有四种结果，全部列出。
aa = [a, b, c, d]
for i in aa:
    if gmpy2.is_prime(i):
        q=i
        print(q)
        print(c3==pow(q, 2, p2*q2))
        break

c = 69544098122008365404362084363106703100129828060729951875286300108187409752434091431958070449710849545293894427509731332109603391232669996343824626329922214945852346904863792615793077092573477272770896080330100575733798947163067912513775789041009052964547466568583353539184274864951400026558080635235037201971
e=65537
n=p*q
phi=(p-1)*(q-1)
d=libnum.invmod(e,phi)
print(d)
print(c)
m=pow(c,d,n)
print(m)
print(libnum.n2s(int(m)))
